CSE 373: Data Structures and Algorithms

Winter 2000

Assignment 3 Chapter 4 Due January 28, 2000

 

Please include your name and student id # on what you turn in.

 

  1. Exercise 4.9 (4.9 in C++ book)

 

  1. Exercise 4.23 (4.27 in C++ book) but only do it for keys 3 and 9 (if you can do those two you’ll understand the general idea of splaying)

 

  1. Exercise 4.24 (4.28 in C++ book) but delete the key 6 from the original figure, not the resulting tree from the preceding problem.

 

  1. Starting with the 2-3 tree on page 134 show the results of adding the key 64.  Then show the results of deleting the key value 17.  For those without the C book here is a crude representation of the starting 2-3 tree.

                                                                                                                                                     

                _________________
               (_______22:-______)
               /                  \
              /                    \
       ____ _/                      \_______
      ( 16:- )                      ( 41:58 )
      /      \                     /    |    \
 ____/____   _\_____    __________/  ___|___  \__________
[ 8,11,12 ] [ 16,17 ]  [ 22,23,31 ] [ 41,52 ] [ 58,59,61 ]

 

  1. Assume you’ve been asked to design a set of routines to traverse a binary search tree and the data structure you are given has three pointers, a parent pointer, left child pointer, and right child pointer. 

        typedef struct _TREE_NODE {
            struct _TREE_NODE *Parent;
            struct _TREE_NODE *LeftChild;
            struct _TREE_NODE *RightChild;
        } TREE_NODE *PTREE_NODE;

    Assume also that for the root node’s parent point is null.  With this structure describe four algorithms that given any node in the tree will return

    (1) the sub-tree predecessor,
    (2) the sub-tree successor,
    (3) the complete-tree predecessor, and
    (4) the complete-tree successor. 

    By sub-tree I mean that the node you are given should be treated as the root of its little tree, even though it may not be.  Therefore the sub-tree procedure only considers direct descendants of the node, whereas the complete-tree procedure needs to potentially consider all the nodes in the entire tree.  Each routine can also return NULL if the node does not have a successor predecessor.  For example, in the following tree the sub-tree predecessor of C if null while its complete tree predecessor is A.

          A
         / \
        B   C
       / \   \
      D   E   F

  2. [Once again not graded]  How much time did you spend on this homework assignment?  On a scale from 1 to 10 (1 being way too easy, 5 being just about right, and 10 being way too hard) how would you rate this for a weekly homework assignment?